package Sort2017;

/**
 * 堆排序
 * Created by 雷文康 on 2017/12/25.
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] array={9,7,8,6,5,4,3,2,1};
        heapSort(array);
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]);
        }
    }
    public static void heapSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length - 1);
        }
        for (int i = array.length - 1; i >= 0; i--) {
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            adjustHeap(array, 0, i - 1);
        }
    }

    private static void adjustHeap(int[] array, int index, int end) {
        for (int i = 2 * index + 1; i <= end; i = 2 * i + 1) {
             if(i < end && array[i] < array[i + 1]){
                 i++;
             }
             if (array[i] <= array[index]){
                 break;
             }
             int temp = array[i];
             array[i] = array[index];
             array[index] = temp;
             index = i;
        }
    }
}
